package org.example;

public class Test2 {
    //leetcode 19 删除链表的倒数第N个节点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

    /**
     * 不引入哨兵节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //通过快慢指针来找到要删除的节点的位置
        ListNode slow = head, fast = head;
        while (fast != null && n + 1 > 0) {
            fast = fast.next;
            n--;
        }
        //这种情况就表示要删除的节点是头结点
        if (fast == null && n == 0) {
            head = head.next;
            return head;
        }
        if (fast != null) {
            while (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        slow.next = slow.next.next;
        return head;
    }

    /**
     * 引入哨兵节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        //通过快慢指针来找到要删除的节点的位置
        ListNode phead = new ListNode();
        phead.next = head;
        ListNode slow = phead, fast = phead;
        while (fast != null && n + 1 > 0) {
            fast = fast.next;
            n--;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return phead.next;
    }
}
